import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:墨琦
 * Data:2023-04-22
 * Time:18:22
 */
public class Text {
    public static boolean isSameTree1(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
        {
            return true;
        }
        else if(p==null||q==null)
        {
            return false;
        }
        if(p.val!=q.val)
        {
            return false;
        }
        else
        { return isSameTree1(p.left,q.left)&&isSameTree1(p.right,q.right);
        }
    }

    public static boolean isSametree(TreeNode root, TreeNode subRoot)
    {
        if(root==null&&subRoot==null)
        {
            return true;
        }
        else if(root==null||subRoot==null)
        {
            return false;
        }
        if(root.val!=subRoot.val){
            return false;
        }
        return isSametree(root.left,subRoot.left)&&isSametree(root.right,subRoot.right);
    }

    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null)
        {
            return false;
        }
        else if(root!=null&&subRoot==null)
        {
            return false;
        }
        return isSametree(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    //前序遍历
    public static void preOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
    //中序遍历
    public static void inOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                cur = node.right;
            }
        }
    }
    //后序遍历
    public static void postOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }

    public static void main(String[] args) {
            TreeNode fw=new TreeNode(10);
            TreeNode fw1=new TreeNode(15);
    }
}
